package Leetcode;

import base.TreeNode;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Stack;

/**
 * @Author piper
 * @Date 2019/10/25 9:56 上午
 */
public class 力扣100_相同的树 {

    /**
     * 遍历两颗二叉树 然后比对是否相同
     * 效率较低 考验二叉树遍历
     */
    static boolean isSameTree(TreeNode p, TreeNode q) {
        Context context = new Context(new PreOrder());
        Stack s1 = new Stack();
        Stack s2 = new Stack();

        context.order(p, s1);
        context.order(q, s2);

        if (s1.size() != s2.size()) {
            return false;
        }

        while (!s1.empty() && !s2.empty()) {
            if (!s1.pop().equals(s2.pop())) {
                return false;
            }
        }

        return true;
    }

    /**
     * 官网算法 递归（树的前序遍历 递归法）
     */
    static boolean isSameTree1(TreeNode p, TreeNode q) {
        // p and q are both null
        if (p == null && q == null) return true;
        // one of p and q is null
        if (q == null || p == null) return false;
        if (p.val != q.val) return false;
        return isSameTree1(p.right, q.right) && isSameTree1(p.left, q.left);
    }

    /**
     * 官网算法 迭代（树的层级遍历 迭代法）
     */
    static boolean isSameTree2(TreeNode p, TreeNode q) {
        boolean check = check(p, q);
        if (!check) return false;

        Deque<TreeNode> deP = new ArrayDeque<>();
        Deque<TreeNode> deQ = new ArrayDeque<>();
        deP.addLast(p);
        deQ.addLast(q);

        while (!deP.isEmpty()) {
            p = deP.removeFirst();
            q = deQ.removeFirst();

            if (!check(p, q)) return false;
            if (p != null) {
                if (!check(p.left, q.left)) return false;
                if (p.left == null) {
                    deP.addLast(p.left);
                    deQ.addLast(q.left);
                }

                if (!check(p.right, q.right)) return false;
                if (p.right == null) {
                    deP.addLast(p.right);
                    deQ.addLast(q.right);
                }
            }
        }

        return true;
    }

    static boolean check(TreeNode p, TreeNode q) {
        // p and q are both null
        if (p == null && q == null) return true;
        // one of p and q is null
        if (q == null || p == null) return false;
        if (p.val != q.val) return false;
        return true;
    }

    public static void main(String[] args) {
        TreeNode t1 = new TreeNode(1);
        TreeNode t2 = new TreeNode(2);
        TreeNode t3 = new TreeNode(3);
        t1.left = t2;
        t1.right = t3;

        TreeNode n1 = new TreeNode(1);
        TreeNode n2 = new TreeNode(2);
        TreeNode n3 = new TreeNode(3);
        n1.left = n2;
        n1.right = n3;

        System.out.println(isSameTree2(t1, n1));
    }

}

//策略容器
class Context {
    Strage strage;

    public Context() {
    }

    public Context(Strage strage) {
        this.strage = strage;
    }

    public void order(TreeNode p, Stack s) {
        strage.order(p, s);
    }
}

// 迭代策略
interface Strage {
    void order(TreeNode p, Stack s);
}

//策略具体实现 前序遍历（迭代）
class PreOrder implements Strage {
    @Override
    public void order(TreeNode p, Stack s) {
        if (p != null) {
            s.push(p.val);
            order(p.left, s);
            order(p.right, s);
        } else {
            s.push(-1);
        }
    }
}

//策略具体实现 中序遍历（迭代）
class InOrder implements Strage {
    @Override
    public void order(TreeNode p, Stack s) {
        if (p != null) {
            order(p.left, s);
            s.push(p.val);
            order(p.right, s);
        } else {
            s.push(-1);
        }
    }
}

//策略具体实现 后序遍历（迭代）
class PostOrder implements Strage {
    @Override
    public void order(TreeNode p, Stack s) {
        if (p != null) {
            order(p.left, s);
            order(p.right, s);
            s.push(p.val);
        } else {
            s.push(-1);
        }
    }
}
